package LeetCode.tree;

import com.sun.imageio.plugins.common.I18N;

import java.io.BufferedInputStream;
import java.text.ParseException;
import java.text.SimpleDateFormat;
import java.util.*;

public class BinSearchTree {
    int data ;
    BinSearchTree left;
    BinSearchTree right;

    public BinSearchTree(int data, BinSearchTree left, BinSearchTree right){
        this.data = data;
        this.left = left;
        this.right = right;
    }

    public BinSearchTree(){

    }


    public static BinSearchTree createBintree(){
        BinSearchTree L2 = new BinSearchTree(4,null,null);
        BinSearchTree R2 = new BinSearchTree(8,null,null);
        BinSearchTree L3 = new BinSearchTree(12,null,null);
        BinSearchTree R3 = new BinSearchTree(16,null,null);
        BinSearchTree L1 = new BinSearchTree(6,L2,R2);
        BinSearchTree R1 = new BinSearchTree(14,L3,R3);
        BinSearchTree T = new BinSearchTree(10,L1,R1);
        return T;
    }

    //前序遍历
    public static void RuPosOrder(BinSearchTree node){
        if (node != null) {
            System.out.println(node.data);
            RuPosOrder(node.left);
            RuPosOrder(node.right);

        }
    }


    //非递归前序遍历
    public static void NonRuPosOrder(BinSearchTree root){
        List<Integer> ans = new LinkedList<Integer>();
        Stack<BinSearchTree> stack = new Stack<BinSearchTree>();
        BinSearchTree node = root;

    }


    //中序遍历
    public static void InOrder(BinSearchTree node, List inOrderList){
        if(node != null){
            InOrder(node.left,inOrderList);
            //System.out.println(node.data);
            inOrderList.add(node.data);
            InOrder(node.right,inOrderList);
        }
    }
    //非递归中序遍历
    public static void nonruInorder(BinSearchTree root){
        Stack<BinSearchTree> stack =  new Stack<BinSearchTree>();
        BinSearchTree node = root;
        while(node != null || !stack.isEmpty()){
            while(node != null){
                stack.push(node);
                node = node.left;
            }
            if(!stack.isEmpty()){
                node = stack.pop();
                System.out.println(node.data);
                node = node.right;
            }
        }

    }




    //后序遍历


    //验证二叉树是否是二叉搜索树,Java 搜索二叉树的中序遍历结果应当是一个递增数列
    public static boolean isValidBST(BinSearchTree head){
        List<Integer> ans = new LinkedList<Integer>();
        Stack<BinSearchTree> stack = new Stack<BinSearchTree>();
        BinSearchTree node = head;
        while(node != null || !stack.isEmpty()){
            while(node != null){
                stack.push(node);
                node = node.left;
            }
            if(!stack.isEmpty()){
                node = stack.pop();
                ans.add(node.data);
                node = node.right;

            }
        }
        if(ans.size()<2){
            return true;
        }
        for(int i=0;i<ans.size()-1;i++){
            if(ans.get(i)>ans.get(i+1)){
                return false;
            }
        }
        return true;
    }

    public static void main(String[] args) throws ParseException {
//        BinSearchTree node = BinSearchTree.createBintree();
//        List<Integer> inOrderList = new ArrayList<Integer>();
//        BinSearchTree.InOrder(node,inOrderList);
//        for (int i=0;i<inOrderList.size();i++) {
//            System.out.println(inOrderList.get(i));
//        }
//        BinSearchTree.RuPosOrder(node);
        //BinSearchTree.nonruInorder(node);

        //System.out.println(BinSearchTree.isValidBST(node));

//        SimpleDateFormat sdf = new SimpleDateFormat("yyyy-MM-dd HH:mm:ss");
//        String str = "2020-09-15T08:42:08.101Z".replace("T"," ").substring(0,19);
//        System.out.println(str);
//
//        Date date = sdf.parse(str);
//        System.out.println("字符串转换成时间:" + date);

        int[] sortArray = {7,6,5,20,15,9,10,8};

    }
}
